Воєводін Вл.В.
Про те, що десь існують якісь містичні "дуже потужні" комп'ютери чув, напевно, кожен. Справді, не так давно було багато розмов про поставку в Гідрометеоцентр Росії могутніх комп'ютерів фірми Cray Research. У листопаді 1999 року відбулося офіційне відкриття Міжвідомчої суперкомп'ютерного центру, який зараз має комп'ютер з 768 процесорами. Знову ж таки, якщо комп'ютер з ім'ям Deep Blue обіграв самого Гаррі Каспарова, то він, погодьтеся - і тут інтуїція Вас не підвела, ну ніяк не може бути простою персоналкой.
Для багатьох подібні комп'ютери так і залишаються таємницею за сімома печатками, якоїсь TERRA INCOGNITA, з якою асоціації завжди пов'язані з чимось більшим: величезні розміри, великі завдання, великі фірми і компанії, неймовірні швидкості роботи або щось інше, але обов'язково це буде "на межі", для чого "звичайного" явно мало, а підійде тільки "супер", суперкомп'ютер або супер-ЕОМ. У цьому інтуїтивному сприйнятті є неабияка частка істини, оскільки до класу супер-ЕОМ належать лише ті комп'ютери, які мають максимальну продуктивність в даний час.
Швидкий розвиток комп'ютерної індустрії визначає відносність даного поняття - те, що десять років тому можна було назвати суперкомп'ютером, сьогодні під це визначення вже не потрапляє. Наприклад, продуктивність персональних комп'ютерів, що використовують Pentium-III/500MHz, порівнянна з продуктивністю суперкомп'ютерів початку 70-х років, проте за сьогоднішніми мірками суперкомп'ютерами не є ні ті, ні інші.
У будь-якому комп'ютері всі основні параметри тісно пов'язані. Важко собі уявити універсальний комп'ютер, що має високу швидкодію і мізерну оперативну пам'ять, або величезну оперативну пам'ять і невеликий обсяг дисків. За логікою, робимо висновок: супер-ЕОМ це комп'ютери, які мають у даний час не тільки максимальну продуктивність, а й максимальний об'єм оперативної і дискової пам'яті (питання про спеціалізований ПЗ, за допомогою якого можна ефективно всім цим скористатися, поки залишимо осторонь).
Так про що ж мова і які суперкомп'ютери існують в даний час в світі? Ось лише кілька параметрів, що дають досить промовисту характеристику машин цього класу. Комп'ютер ASCI WHITE, що займає перше місце в списку п'ятисот найпотужніших комп'ютерів світу, об'єднує 8192 процесора Power 3 з загальної оперативною пам'яттю в 4 терабайта і продуктивністю більше 12 трильйонів операцій за секунду.
Супер-ЕОМ і надвисока продуктивність: навіщо?
Прості розрахунки показують, що конфігурації подібних систем можуть коштувати не один мільйон доларів США - заради інтересу прикиньте, скільки коштують, скажімо, лише 4 Тбайта оперативної пам'яті? Виникає цілий ряд природних питань: які завдання настільки важливі, що потрібні комп'ютери вартістю кілька мільйонів доларів? Або, які завдання настільки складні, що хорошого Пентіума не достатньо? На ці та подібні їм питання хотілося б знайти розумні відповіді.
Для того, щоб оцінити складність розв'язуваних на практиці завдань, візьмемо конкретну предметну область, наприклад, оптимізацію процесу видобутку нафти. Маємо підземний нафтової резервуар з яким-то число пробурених свердловин: за одними на поверхню відкачується нафту, за іншими назад закачується вода. Потрібно змоделювати ситуацію в даному резервуарі, щоб оцінити запаси нафти або зрозуміти необхідність у додаткових свердловинах.
Приймемо спрощену схему, при якій моделируемая область відображається в куб, проте і її буде достатньо для оцінки числа необхідних арифметичних операцій. Розумні розміри куба, при яких можна отримувати правдоподібні результати - це 100 * 100 * 100 точок. У кожній точці куба треба обчислити від 5 до 20 функцій: три компоненти швидкості, тиск, температуру, концентрацію компонент (вода, газ і нафта - це мінімальний набір компонентів, у більш реалістичних моделях розглядають, наприклад, різні фракції нафти). Далі, значення функцій знаходяться як рішення нелінійних рівнянь, що вимагає від 200 до 1000 арифметичних операцій. І нарешті, якщо досліджується нестаціонарний процес, тобто потрібно зрозуміти, як ця система веде себе в часі, то робиться 100-1000 кроків за часом. Що вийшло:
106 (точок сітки) * 10 (функцій) * 500 (операцій) * 500 (кроків за часом) = 2.5 * 1012
2500 млрд арифметичних операцій для виконання одного лише розрахунку! А зміна параметрів моделі? А відстеження поточної ситуації при зміні вхідних даних? Подібні розрахунки необхідно робити багато разів, що накладає дуже жорсткі вимоги на продуктивність використовуваних обчислювальних систем.
Приклади використання суперкомп'ютерів можна знайти не тільки в нафтовидобувній промисловості. Ось лише невеликий список областей людської діяльності, де використання суперкомп'ютерів дійсно необхідно:
автомобілебудування
нафто-і газовидобування
фармакологія
прогноз погоди та моделювання зміни клімату
сейсморозвідка
проектування електронних пристроїв
синтез нових матеріалів
і багато, багато інших
У 1995 році корпус автомобіля Nissan Maxima вдалося зробити на 10% міцніше завдяки використанню суперкомп'ютера фірми Cray (The Atlanta Journal, 28 травня, 1995). За допомогою нього були знайдені не тільки слабкі точки кузова, але і найбільш ефективний спосіб їх видалення.
За даними Марка Міллера (Mark Miller, Ford Motor Company), для виконання crash-тестів, при яких реальні автомобілі розбиваються об бетонну стіну з одночасним вимірюванням необхідних параметрів, зйомкою і наступною обробкою результатів, компанії Форд знадобилося б від 10 до 150 прототипів нових моделей при загальних витратах від 4 до 60 мільйонів доларів. Використання суперкомп'ютерів дозволило скоротити число прототипів на одну третину.
Зовсім недавній приклад - це розвиток однієї з найбільших світових систем резервування Amadeus, використовуваної тисячами агенств з 180000 терміналів у більш ніж ста країнах. Установка двох серверів Hewlett-Packard T600 по 12 процесорів у кожному дозволила довести ступінь оперативної доступності центральної системи до 99.85% при поточній завантаженні близько 60 мільйонів запитів на добу.
І подібні приклади можна знайти всюди. Свого часу дослідники фірми DuPont шукали заміну хлорофлюорокарбону. Потрібно було знайти матеріал, що має ті ж позитивні якості: незаймистість, стійкість до корозії і низьку токсичність, але без шкідливого впливу на озоновий шар Землі. За один тиждень були проведені необхідні розрахунки на суперкомп'ютері з загальними витратами близько 5 тисяч доларів. За оцінками фахівців DuPont, використання традиційних експериментальних методів досліджень зажадало б близько трьох місяців і 50 тисяч доларів і це без урахування часу, необхідного на синтез і очищення необхідної кількості речовини.
Збільшення продуктивності ЕОМ, за рахунок чого?
А чому суперкомп'ютери вважають так швидко? Варіантів відповіді може бути декілька, серед яких два мають явну перевагу: розвиток елементної бази і використання нових рішень в архітектурі комп'ютерів.
Спробуємо розібратися, який із цих факторів виявляється вирішальним для досягнення рекордної продуктивності. Звернемося до відомим історичним фактам. На одному з перших комп'ютерів світу - EDSAC, який з'явився в 1949 році в Кембриджі і мав час такту 2 мікросекунди (2 * 10-6 секунди), можна було виконати 2 * n арифметичних операцій за 18 * n мілісекунд, тобто в середньому 100 арифметичних операцій в секунду. Порівняємо з одним обчислювальним вузлом сучасного суперкомп'ютера Hewlett-Packard V2600: час такту приблизно 1.8 наносекунди (1.8 * 10-9 секунд), а пікова продуктивність близько 77 млрд арифметичних операцій в секунду.
Що ж виходить? За півстоліття продуктивність комп'ютерів виросла більш, ніж в сімсот мільйонів разів. При цьому виграш у швидкодії, пов'язаний із зменшенням часу такту з 2 мікросекунд до 1.8 наносекунд, складає лише близько 1000 разів. Звідки ж узялася інше? Відповідь очевидна - використання нових рішень в архітектурі комп'ютерів. Основне місце серед них займає принцип паралельної обробки даних, що втілює ідею одночасного (паралельного) виконання кількох дій.
Паралельна обробка даних на ЕОМ
Паралельна обробка даних, втілюючи ідею одночасного виконання кількох дій, має два різновиди: конвеєрні і власне паралельність. Обидва види паралельної обробки інтуїтивно зрозумілі, тому зробимо лише невеликі пояснення.
Паралельна обробка. Якщо якийсь пристрій виконує одну операцію за одиницю часу, то тисячу операцій воно виконає за тисячу одиниць. Якщо припустити, що є п'ять таких же незалежних пристроїв, здатних працювати одночасно, то ту ж тисячу операцій система з п'яти пристроїв може виконати вже не за тисячу, а за двісті одиниць часу. Аналогічно система з N пристроїв ту ж роботу виконає за 1000 / N одиниць часу. Подібні аналогії можна знайти і в житті: якщо один солдат скопає город за 10 годин, то рота солдатів з п'ятдесяти чоловік з такими ж здібностями, працюючи одночасно, впораються з тією ж роботою за 12 хвилин - принцип паралельності в дії!
До речі, піонером в паралельній обробці потоків даних був академік А. А. Самарський, що виконував на початку 50-х років розрахунки, необхідні для моделювання ядерних вибухів. Самарський вирішив цю задачу, посадивши кілька десятків панянок з арифмометром за столи. Панянки передавали дані один одному просто на словах і відкладали необхідні цифри на арифмометрах. Таким чином, зокрема, була розрахована еволюція вибухової хвилі. Роботи було багато, панночки втомлювалися, а Олександр Андрійович ходив між ними і підбадьорював. Це, можна сказати, і була перша паралельна система. Хоча розрахунки водневої бомби були майстерно проведені, точність їх була дуже низька, тому що вузлів у використовуваній сітці було мало, а час рахунку виходило занадто великим.
Конвеєрна обробка. Що необхідно для складання двох дійсних чисел, представлених у формі з плаваючою комою? Ціле безліч дрібних операцій таких, як порівняння порядків, вирівнювання порядків, складання мантис, нормалізація і т.п. Процесори перших комп'ютерів виконували всі ці "мікрооперації" для кожної пари аргументів послідовно одна за одною до тих пір, поки не доходили до остаточного результату, і лише після цього переходили до обробки наступної пари доданків.
Ідея конвеєрної обробки полягає у виділенні окремих етапів виконання спільної операції, причому кожен етап, виконавши свою роботу, передавав би результат наступного, одночасно приймаючи нову порцію вхідних даних. Отримуємо очевидний виграш у швидкості обробки за рахунок поєднання перш рознесені в часі операцій. Припустимо, що в операції можна виділити п'ять мікрооперацій, кожна з яких виконується за одну одиницю часу. Якщо є одне неподільне послідовне пристрій, то 100 пар аргументів воно обробить за 500 одиниць. Якщо кожну мікрооперацію виділити в окремий етап (або інакше кажуть - ступінь) конвеєрного пристрою, то на п'ятій одиниці часу на різній стадії обробки такого пристрою будуть знаходиться перші п'ять пар аргументів, а весь набір із ста пар буде оброблений за 5 +99 = 104 одиниці часу - прискорення в порівнянні з послідовним пристроєм майже в п'ять разів (по числу ступенів конвеєра).
Здавалося б конвеєрну обробку можна з успіхом замінити звичайним паралелізмом, для чого продублювати основний пристрій стільки разів, скільки ступенів конвеєра передбачається виділити. У самому справі, п'ять пристроїв попереднього прикладу оброблять 100 пар аргументів за 100 одиниць часу, що швидше часу роботи конвеєрного пристрою! У чому ж справа? Відповідь проста, збільшивши в п'ять разів число пристроїв, ми значно збільшуємо як обсяг апаратури, так і її вартість. Уявіть собі, що на автозаводі вирішили прибрати конвеєр, зберігши темпи випуску автомобілів. Якщо раніше на конвеєрі одночасно перебувала тисяча автомобілів, то діючи за аналогією з попереднім прикладом треба набрати тисячу бригад, кожна з яких (1) в змозі повністю зібрати автомобіль від початку до кінця, виконавши сотні різного роду операцій, і (2) зробити це за Водночас, що машина раніше знаходилася на конвеєрі. Представили собівартість такого автомобіля? Ні? Згоден, важко, хіба що Ламборгіні приходить на розум, але тому і виникла конвеєрна обробка ...
Коротка історія появи паралелізму в архітектурі ЕОМ
Сьогодні паралелізмом в архітектурі комп'ютерів уже мало кого здивуєш. Всі сучасні мікропроцесори, будь то Pentium III або PA-8700, MIPS R14000, Е2К або Power3 використовують той чи інший вид паралельної обробки. У ядрі Pentium 4 на різних стадіях виконання може одночасно перебувати до 126 мікрооперацій. На презентаціях нових чіпів і в прес-релізах корпорацій це підноситься як останнє слово техніки та передовий край науки, і це дійсно так, якщо розглядати реалізацію цих принципів у мініатюрних рамках одного кристала.
Разом з тим, самі ці ідеї з'явилися дуже давно. Спочатку вони впроваджувалися в самих передових, а тому одиничних, комп'ютерах свого часу. Потім після належної відпрацювання технології і здешевлення виробництва вони спускалися в комп'ютери середнього класу, і нарешті сьогодні все це в повному обсязі втілюється в робочих станціях і персональних комп'ютерах.
Для того щоб переконатися, що всі основні нововведення в архітектурі сучасних процесорів насправді використовуються ще з часів, коли ні мікропроцесорів, ні поняття суперкомп'ютерів ще не було, спробуємо в історію, почавши практично з моменту народження перших ЕОМ.
IBM 701 (1953), IBM 704 (1955): розрядно-паралельна пам'ять, розрядно-паралельна арифметика.
Всі самі перші комп'ютери (EDSAC, EDVAC, UNIVAC) мали розрядно-послідовну пам'ять, з якої слова зчитувалися послідовно біт за бітом. Першим комерційно доступним комп'ютером, використовують розрядно-паралельну пам'ять (на CRT) і розрядно-паралельну арифметику, став IBM 701, а найбільшу популярність отримала модель IBM 704 (продано 150 екз.), В якій, крім сказаного, була вперше застосована пам'ять на феритових сердечниках і апаратне АУ з плаваючою крапкою.
IBM 709 (1958): незалежні процесори введення / виводу.
Процесори перших комп'ютерів самі керували вводом / виводом. Однак швидкість роботи найшвидшого зовнішнього пристрою, а на ті часи це магнітна стрічка, була в 1000 разів менше швидкості процесора, тому під час операцій введення / виведення процесор фактично простоював. У 1958р. до комп'ютера IBM 704 приєднали 6 незалежних процесорів введення / виводу, які після отримання команд могли працювати паралельно з основним процесором, а сам комп'ютер перейменували на IBM 709. Дана модель вийшла напрочуд вдалою, тому що разом з модифікаціями було продано близько 400 екземплярів, причому останній був вимкнений у 1975 році - 20 років існування!
IBM STRETCH (1961): випереджаюче перегляд вперед, розшарування пам'яті.
У 1956 році IBM підписує контракт з Лос-Аламоської наукової лабораторії на розробку комп'ютера STRETCH, що має дві принципово важливі особливості: випереджаюче перегляд вперед для вибірки команд і розшарування пам'яті на два банки для узгодження низькій швидкості вибірки з пам'яті і швидкості виконання операцій.
ATLAS (1963): конвеєр команд.
Вперше конвеєрний принцип виконання команд був використаний в машині ATLAS, розробленої в Манчестерському університеті. Виконання команд розбито на 4 стадії: вибірка команди, обчислення адреси операнда, вибірка операнда і виконання операції. Конвейеризация дозволила зменшити час виконання команд з 6 мкс до 1,6 мкс. Комп'ютер зробив величезний вплив, як на архітектуру ЕОМ, так і на програмне забезпечення: в ньому вперше використана мультипрограмна ОС, заснована на використанні віртуальної пам'яті і системи переривань.
CDC 6600 (1964): незалежні функціональні пристрої.
Фірма Control Data Corporation (CDC) при безпосередній участі одного з її засновників, Сеймура Р. Крея (Seymour R. Cray) випускає комп'ютер CDC-6600 - перший комп'ютер, в якому використовувалося кілька незалежних функціональних пристроїв. Для порівняння з сьогоднішнім днем наведемо деякі параметри комп'ютера:
час такту 100нс,
продуктивність 2-3 млн. операцій у секунду,
оперативна пам'ять розбита на 32 банку за 4096 60-ти розрядних слів,
цикл пам'яті 1мкс,
10 незалежних функціональних пристроїв.
Машина мала величезний успіх на науковому ринку, активно витісняючи машини фірми IBM.
CDC 7600 (1969): конвеєрні незалежні функціональні пристрої.
CDC випускає комп'ютер CDC-7600 з вісьмома незалежними конвеєрними функціональними пристроями - поєднання паралельної і конвеєрної обробки. Основні параметри:
такт 27,5 нс,
10-15 млн. опер / сек.,
8 конвеєрних ФУ,
2-х рівнева пам'ять.
ILLIAC IV (1974): матричні процесори.
Проект: 256 процесорних елементів (ПЕ) = 4 квадранта по 64ПЕ, можливість реконфігурації: 2 квадранта по 128ПЕ або 1 квадрант з 256ПЕ, такт 40нс, продуктивність 1Гфлоп;
роботи початі в 1967 році, до кінця 1971 виготовлена система з 1 квадранта, в 1974р. вона введена в експлуатацію, доведення велася до 1975 року;
центральна частина: пристрій управління (УУ) + матриця з 64 ПЕ;
УУ це проста ЕОМ з невеликою продуктивністю, керуюча матрицею ПЕ; всі ПЕ матриці працювали в синхронному режимі, виконуючи в кожен момент часу одну і ту ж команду, що поступила від УУ, але над своїми даними;
ПЕ мав власне АЛП з повним набором команд, ОП - 2Кслова по 64 розряду, цикл пам'яті 350нс, кожен ПЕ мав безпосередній доступ тільки до своєї ВП;
мережа пересилання даних: двовимірний тор із зсувом на 1 по кордоні по горизонталі;
Не дивлячись на результат у порівнянні з проектом: вартість в 4 рази вище, зроблений лише 1 квадрант, такт 80нс, реальна произв-ть до 50Мфлоп - даний проект зробив величезний вплив на архітектуру наступних машин, побудованих за схожим принципом, зокрема: PEPE, BSP , ICL DAP.
CRAY 1 (1976): векторно-конвейєрні процесори
У 1972 році С. Крей залишає CDC і засновує свою компанію Cray Research, що в 1976р. випускає перший векторно-конвеєрний комп'ютер CRAY-1: час такту 12.5нс, 12 конвеєрних функціональних пристроїв, пікова продуктивність 160 мільйонів операцій в секунду, оперативна пам'ять до 1Мслова (слово - 64 розряду), цикл пам'яті 50нс. Головним нововведенням є введення векторних команд, які працюють з цілими масивами незалежних даних і дозволяють ефективно використовувати конвеєрні функціональні пристрої.
Ієрархія пам'яті.
Ієрархія пам'яті пямого відносини до паралелізму не має, проте, безумовно, відноситься до тих особливостей архітектури комп'ютерів, які має величезне значення для підвищення їх продуктивності (згладжування різниці між швидкістю роботи процесора і часом вибірки з пам'яті). Основні рівні: регістри, кеш-пам'ять, оперативна пам'ять, дискова пам'ять. Час вибірки за рівнями пам'яті від дискової пам'яті до регістрів зменшується, вартість у перерахунку на 1 слово (байт) зростає. В даний час, подібна ієрархія підтримується навіть на персональних комп'ютерах.
А що ж зараз використовують у світі?
За яким же напрямках йде розвиток високопродуктивної обчислювальної техніки в даний час? Основних напрямів чотири.
1. Векторно-конвейєрні комп'ютери. Конвеєрні функціональні пристрої та набір векторних команд - це дві особливості таких машин. На відміну від традиційного підходу, векторні команди оперують цілими масивами незалежних даних, що дозволяє ефективно завантажувати доступні конвеєри, тобто команда виду A = B + C може означати складання двох масивів, а не двох чисел. Характерним представником цього напряму є сімейство векторно-конвейєрних комп'ютерів CRAY куди входять, наприклад, CRAY EL, CRAY J90, CRAY T90 (у березні 2000 року американська компанія TERA перекупила підрозділ CRAY у компанії Silicon Graphics, Inc.).
2. Масивно-паралельні комп'ютери з розподіленою пам'яттю. Ідея побудови комп'ютерів цього класу тривіальна: візьмемо серійні мікропроцесори, постачимо кожен своєю локальною пам'яттю, з'єднаємо за допомогою деякої комунікаційного середовища - ось і все. Переваг у такої архітектури маса: якщо потрібна висока продуктивність, то можна додати ще процесорів, якщо обмежені фінанси або заздалегідь відома необхідна обчислювальна потужність, то легко підібрати оптимальну конфігурацію і т.п.
Однак є й вирішальний "мінус", що зводить багато "плюси" нанівець. Справа в тому, що межпроцессорной взаємодія в комп'ютерах цього класу йде набагато повільніше, ніж відбувається локальна обробка даних самими процесорами. Саме тому написати ефективну програму для таких комп'ютерів дуже складно, а для деяких алгоритмів іноді просто неможливо. До даного класу можна віднести комп'ютери Intel Paragon, IBM SP1, Parsytec, в якійсь мірі IBM SP2 і CRAY T3D/T3E, хоча в цих комп'ютерах вплив зазначеного мінуса значно послаблено. До цього ж класу можна віднести і мережі комп'ютерів, які все частіше розглядають як дешеву альтернативу вкрай дорогим суперкомп'ютерів.
3. Паралельні комп'ютери із загальною пам'яттю. Вся оперативна пам'ять таких комп'ютерів розділяється декількома однаковими процесорами. Це знімає проблеми попереднього класу, але додає нові - число процесорів, що мають доступ до загальної пам'яті, з чисто технічних причин не можна зробити більшим. У даний напрямок входять багато сучасних багатопроцесорні SMP-комп'ютери або, наприклад, окремі вузли комп'ютерів HP Exemplar і Sun StarFire.
4. Останній напрям, строго кажучи, не є самостійним, а швидше є комбінації попередніх трьох. З декількох процесорів (традиційних або векторно-конвейєрних) і загальної для них пам'яті сформуємо обчислювальний вузол. Якщо отриманої обчислювальної потужності не досить, то об'єднаємо декілька вузлів високошвидкісними каналами. Подібну архітектуру називають кластерної, і за таким принципом побудовані CRAY SV1, HP Exemplar, Sun StarFire, NEC SX-5, останні моделі IBM SP2 та інші. Саме цей напрямок є в даний час найбільш перспективним для конструювання комп'ютерів з рекордними показниками продуктивності.
Використання паралельних обчислювальних систем
На жаль дива в житті рідко трапляються. Гігантська продуктивність паралельних комп'ютерів і супер-ЕОМ з лишком компенсується складнощами їх використання. Почнемо з найпростіших речей. У вас є програма і доступ, скажімо, до 256-процесорного комп'ютера. Що ви очікуєте? Та ясно що: ви цілком законно очікуєте, що програма буде виконуватися в 256 разів швидше, ніж на одному процесорі. А от саме цього, швидше за все, і не буде.
Закон Амдала і його наслідки
Припустимо, що у вашій програмі частка операцій, які потрібно виконувати послідовно, дорівнює f, де 0 <= f <= 1 (при цьому частка розуміється не по статичному числу рядків коду, а за кількістю операцій у процесі виконання). Крайні випадки в значеннях f відповідають повністю паралельним (f = 0) і повністю послідовним (f = 1) програмами. Так от, для того, щоб оцінити, яке прискорення S може бути отримано на комп'ютері з 'p' процесорів при даному значенні f, можна скористатися законом Амдала:
Якщо 9 / 10 програми виповнюється паралельно, а 1 / 10 і раніше послідовно, то прискорення більше, ніж у 10 разів одержати в принципі неможливо незалежно від якості реалізації паралельної частини коду і кількості використовуваних процесорів (ясно, що 10 виходить тільки в тому випадку, коли час виконання паралельної частини дорівнює 0).
Подивимося на проблему з іншого боку: а яку ж частину коду треба прискорити (а значить і попередньо досліджувати), щоб отримати заданий прискорення? Відповідь можна знайти в слідстві із закону Амдала: для того щоб прискорити виконання програми в q раз необхідно прискорити не менш, ніж в q раз не менше, ніж (1-1 / q)-у частину програми. Отже, якщо є бажання прискорити програму в 100 разів у порівнянні з її послідовним варіантом, то необхідно отримати не менше прискорення не менше, ніж на 99.99% коду, що майже завжди складає значну частину програми!
Звідси перший висновок - перш, ніж грунтовно переробляти код для переходу на паралельний комп'ютер (а будь-який суперкомп'ютер, зокрема, є таким) треба грунтовно подумати. Якщо оцінивши закладений у програмі алгоритм ви зрозуміли, що частка послідовних операцій велика, то на значне прискорення розраховувати явно не доводиться і потрібно думати про заміну окремих компонент алгоритму.
У ряді випадків послідовний характер алгоритму змінити не так складно. Припустимо, що в програмі є наступний фрагмент для обчислення суми n чисел:
s = 0
Do i = 1, n
s = s + a (i)
EndDo
(Можна теж саме на будь-якому іншому мовою)
За своєю природою він строго послідовний, так як на i-й ітерації циклу потрібно результат з (i-1)-й і всі ітерації виконуються одна за одною. Ми маємо 100% послідовних операцій, а значить і ніякого ефекту від використання паралельних комп'ютерів. Разом з тим, вихід очевидний. Оскільки в більшості реальних програм (питання: а чому в більшості, а не у всіх?) Немає істотної різниці, в якому порядку складати числа, виберемо іншу схему складання. Спочатку знайдемо суму пар сусідніх елементів: a (1) + a (2), a (3) + a (4), a (5) + a (6) і т.д. Зауважимо, що при такій схемі всі пари можна складати одночасно! На наступних кроках будемо діяти абсолютно аналогічно, отримавши варіант паралельного алгоритму.
Здавалося, що в даному випадку всі проблеми вдалося вирішити. Але уявіть, що доступні вам процесори різнорідні за своєю продуктивністю. Значить буде такий момент, коли хтось із них ще трудиться, а хтось вже все зробив і марно простоює в очікуванні. Якщо розкид в продуктивності комп'ютерів великий, то й ефективність всієї системи при рівномірному завантаженні процесорів буде вкрай низькою.
Але підемо далі і припустимо, що всі процесори однакові. Проблеми скінчилися? Знову ні! Процесори виконали свою роботу, але результат-то треба передати іншому для продовження процесу підсумовування ... а на передачу йде час ... і в цей час процесори знову простоюють ...
Словом, змусити паралельну обчислювальну систему або супер-ЕОМ працювати з максимальною ефективність на конкретній програмі це, прямо скажемо, завдання не з простих, оскільки необхідно ретельне узгодження структури програм і алгоритмів з особливостями архітектури паралельних обчислювальних систем.
Заключний питання. Як ви думаєте, чи вірно твердження: чим потужніший комп'ютер, тим швидше на ньому можна вирішити дану задачу?
Заключний відповідь. Ні, це не вірно. Це можна пояснити простим побутовим прикладом. Якщо один землекоп викопає яму 1м * 1м * 1м за 1 годину, то два таких же землекопа це зроблять за 30 хв - в це можна повірити. А за скільки часу цю роботу зроблять 60 землекопів? За 1 хвилину? Звичайно ж ні! Починаючи з деякого моменту вони будуть просто заважати один одному, не прискорюючи, а сповільнюючи процес. Так само і в комп'ютерах: якщо завдання занадто мала, то ми будемо довше займатися розподілом роботи, синхронізацією процесів, складанням результатів тощо, ніж безпосередньо корисною роботою.
Абсолютно ясно, що не все так просто ...